Implement queue using stacks [Two stacks]

Time: O(1); Space: O(N); easy

Implement queue using stacks Implement the following operations of a queue using stacks. * peek() – Get the front element. * push(x) – Push element x to the back of queue. * pop() – Removes the element from in front of queue. * empty() – Return whether the queue is empty.

Example 1:

Input/Output:

  • queue = Queue()

  • queue.push(1)

  • queue.push(2)

  • queue.peek() -> returns 1

  • queue.pop() -> returns 1

  • queue.empty() -> returns False

Notes:

  • Time O(1) amortized

  • You must use only standard operations of a stack - which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, stack may not be supported natively.

  • You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

1. Two Stacks: Push - O(n) per operation, Pop - O(1) per operation.

Algorithm

Push

A queue is FIFO (first-in-first-out) but a stack is LIFO (last-in-first-out). This means the newest element must be pushed to the bottom of the stack. To do so we first transfer all s1 elements to auxiliary stack s2. Then the newly arrived element is pushed on top of s2 and all its elements are popped and pushed to s1.

  • Time: O(n)O(n). Each element, with the exception of the newly arrived, is pushed and popped twice. The last inserted element is popped and pushed once. Therefore this gives 4 n + 24n+2 operations where nn is the queue size. The push and pop operations have O(1)O(1) time complexity.

  • Space: O(n). We need additional memory to store the queue elements.

Pop

The algorithm pops an element from the stack s1, because s1 stores always on its top the first inserted element in the queue. The front element of the queue is kept as front.

  • Time: O(1).

  • Space: O(1).

Empty

Stack s1 contains all stack elements, so the algorithm checks s1 size to return if the queue is empty.

  • Time: O(1).

  • Space: O(1).

Peek

The front element is kept in constant memory and is modified when we push or pop an element.

  • Time: O(1). The front element has been calculated in advance and only returned in peek operation.

  • Space: O(1).

[7]:

class Queue1(object):
    """
    push O(n)
    pop O(1)
    """
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def push(self, x):
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self):
        return self.s1.pop()

    def peek(self):
        return self.s1[-1]

    def empty(self):
        return not self.s1

[8]:

queue = Queue1()
queue.push(1)
queue.push(2)
assert queue.peek() == 1
assert queue.pop() == 1
assert queue.empty() == False

2. Two Stacks: Push - O(1) per operation, Pop - Amortized O(1) per operation.

Algorithm

Push

The newly arrived element is always added on top of stack s1 and the first element is kept as front queue element

Time: O(1). Аppending an element to a stack is an O(1) operation. Space: O(n). We need additional memory to store the queue elements

Pop

We have to remove element in front of the queue. This is the first inserted element in the stack s1 and it is positioned at the bottom of the stack because of stack’s LIFO (last in - first out) policy. To remove the bottom element from s1, we have to pop all elements from s1 and to push them on to an additional stack s2, which helps us to store the elements of s1 in reversed order. This way the bottom element of s1 will be positioned on top of s2 and we can simply pop it from stack s2. Once s2 is empty, the algorithm transfer data from s1 to s2 again.

[9]:

class Queue2(object):
    """
    push O(1)
    pop amortized O(1)
    """
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def push(self, x):
        self.s1.append(x)

    def pop(self):
        self.peek()
        return self.s2.pop()

    def peek(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    def empty(self):
        return not self.s1 and not self.s2

[10]:

queue = Queue2()
queue.push(1)
queue.push(2)
assert queue.peek() == 1
assert queue.pop() == 1
assert queue.empty() == False